package Other.DP;

/**
 * @author:gao
 * @date:2020/7/14
 * @time:14:05
 * @version:0.0.1
 * @description:none
 */


//121. 买卖股票的最佳时机
public class MaxProfitOne {
    public static void main(String[] args) {
//        int[] prices = new int[]{1,2};
//        Solution solution = new Solution();
//        solution.maxProfit(prices);
    }
}

//双指针解法
class Solution000000000 {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<2) return 0;
        int min = prices[0];
        int max = prices[1];
        int minIndex =0;
        int maxIndex = 1;  //用index防止min到max后面
        int ans = max>min?max-min:0;
        for (int i = 1; i <prices.length-1 ; i++) {
            if(min>prices[i]) {
                min = prices[i];
                minIndex=i;
            }
            if(max<prices[i+1]){
                max = prices[i+1];
                maxIndex = i+1;
            }
            if(maxIndex<=minIndex) {
                maxIndex = i + 1;
                max = prices[i+1];
            }
            ans = Math.max(max-min,ans);
        }
        return  ans;
    }
}


//优化空间的dp
class Solution0dddd {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<2) return 0;
        int ans=-1;
        int min=Integer.MAX_VALUE;
        for(int n:prices){
            if(min>n){
                min=n;
            }
            ans = Math.max(ans,n-min);
        }
        return  ans;
    }
}
